package my.tree;

import java.util.Comparator;

/**
 * <p>
 * 平衡二叉搜索树
 * </p>
 *
 * @author AJun
 * @since 2020/8/29
 */
@SuppressWarnings("unused")
public class BBST<E> extends BST<E> {

    public BBST() {
        this(null);
    }

    public BBST(Comparator<E> comparator) {
        super(comparator);
    }

    /**
     * RR 左旋转
     *
     * @param grand 祖父节点
     */
    protected void rotateLeft(Node<E> grand) {
        Node<E> parent = grand.right;
        Node<E> child = parent.left;
        grand.right = child;
        parent.left = grand;

        // 旋转之后的维护
        afterRotate(grand, parent, child);
    }

    /**
     * LL 右旋转
     *
     * @param grand 祖父节点
     */
    protected void rotateRight(Node<E> grand) {
        Node<E> parent = grand.left;
        Node<E> child = parent.right;
        grand.left = child;
        parent.right = grand;

        // 旋转之后的维护
        afterRotate(grand, parent, child);
    }

    /**
     * 旋转后的节点维护
     *
     * @param grand  祖父节点
     * @param parent 父节点
     * @param child  父节点的左子节点或右子节点
     */
    protected void afterRotate(Node<E> grand, Node<E> parent, Node<E> child) {
        // 让 parent 成为这棵树的根节点
        parent.parent = grand.parent;
        if (grand.isLeftChild()) {
            grand.parent.left = parent;
        } else if (grand.isRightChild()) {
            grand.parent.right = parent;
        } else {
            // grand 是 root 节点
            root = parent;
        }

        // 更新 child 的 parent
        if (child != null) {
            child.parent = grand;
        }

        // 更新 grand 的 parent
        grand.parent = parent;
    }

}
